#include <iostream>
#include <functional>
#include "treenode.h"
using namespace std;

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        function<bool(TreeNode*, TreeNode*)> isSameTree = [&isSameTree](TreeNode *root1, TreeNode *root2) -> bool {
            return root2 == nullptr || (root1 != nullptr && root2 != nullptr && root1->val == root2->val && isSameTree(root1->left, root2->left) && isSameTree(root1->right, root2->right));
        };
        return pRoot1!= nullptr && pRoot2 != nullptr && ((pRoot1->val == pRoot2->val && isSameTree(pRoot1, pRoot2)) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2));
    }
};
int main() {
    TreeNode *root1 = new TreeNode(8, new TreeNode(8, new TreeNode(9), new TreeNode(2, new TreeNode(4), new TreeNode(7))), new TreeNode(7));
    TreeNode *root2 = new TreeNode(8, new TreeNode(9), new TreeNode(2));
    cout << Solution().HasSubtree(root1, root2) << endl;
    return 0;
}